package binarytree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Stack;

/**
 * @ClassName UnRecursiveBinaryTree
 * @Description TODO
 * @Author Admin
 * @Date 2021/12/16 10:58
 * @Version 1.0
 * 不用递归，用栈实现先序，效率高一点
 */
public class UnRecursiveBinaryTree {
    //栈实现二叉树先续遍历
    public static void preOrder(BinaryTreeNode node){
        if (node!=null){
            Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
            stack.add(node);
            while (!stack.isEmpty()){
                node=stack.pop();
                System.out.println(node.value+" ");
                if (node.right!=null){
                    stack.push(node.right);
                }
                if (node.left!=null){
                    stack.push(node.left);
                }

            }

        }

    }
    //栈实现二叉树中续遍历
    public static void inOrder(BinaryTreeNode node){
        if (node!=null){
            Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
            while (node!=null||!stack.isEmpty()){
                while (node!=null){
                    stack.push(node);
                    node=node.left;
                }
                node=stack.pop();
                System.out.println(node.value);
                node=node.right;


            }

        }
    }
    //栈实现二叉树后续遍历 思路：后续遍历是 左 右 根   我们只要按照先序遍历的方法遍历出 根 右 左 在反转一下就得到了后续遍历
    public static void postOrder(BinaryTreeNode node){
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (node!=null){
            Stack<BinaryTreeNode> stack = new Stack<>();
            stack.push(node);
            while (!stack.isEmpty()){
                node=stack.pop();
                list.add(node.value);
                if (node.left!=null){
                    stack.push(node.left);
                }
                if (node.right!=null){
                    stack.push(node.right);
                }
            }
            //集合反转
            Collections.reverse(list);
            System.out.println(list);

   }
    }



}
